Not applicable
Not applicable
Not applicable
1. Field of the Invention
The invention is related to the field of telecommunications, and in particular, to a software model for optical communication networks.
2. Description of the Prior Art
Wavelength-Division Multiplexing (WDM) is a key approach to increase the bandwidth of an optical network. As WDM technology continues to mature, there exists a large gap between the capacity of a WDM channel such as OC-48, OC-192 or OC-768 and the bandwidth requirement of a typical connection request such as STS-1, OC-3, and OC-12. If the entire bandwidth of a wavelength channel is allocated to a low rate connection, a large portion of the transmission capacity is wasted. In order to use the network resources efficiently, low-speed traffic streams need to be efficiently multiplexed, or xe2x80x9cgroomedxe2x80x9d, onto high speed lightpaths.
One problem with traffic grooming is the determination of how to set up lightpaths to satisfy connection request based on a set of connection requests and a network configuration including the physical topology, where each edge is a physical link, the number of transceivers at each node, the number of wavelengths on each fiber, and the capacity of each wavelength. Because of the sub-wavelength granularity of the connection requests, one or more connections can be multiplexed on the same lightpath.
With static traffic, the set of all connection requests is provided in advance. With dynamic traffic, connection requests are provided one at a time. Traffic grooming with static traffic has two optimization problems. One problem in a non-blocking scenario, where the network has enough resources to carry all of the connection requests, is to minimize the network cost while satisfying all the requests, where one cost component is the number of wavelength links and a wavelength-link is defined as a wavelength in a fiber-link. Another problem in a blocking scenario, where not all connections can be set up due to resource limitations, is to maximize the network throughput. With dynamic traffic, one optimization problem is to minimize the network resources used for each request, which implicitly attempts to minimize the blocking probability for future requests.
Traffic grooming is usually divided into four sub-problems, which are not necessarily independent: (1) determining the virtual topology that consists of lightpaths, (2) routing the lids over the physical topology, (3) performing wavelength assignment to the lightpaths, and (4) muting the traffic on the virtual topology. The virtual topology design problem is conjectured to be NP-hard. In addition, routing and wavelength assignment (RWA) is also NP-hard. Therefore, traffic grooming in a mesh network is also a NP-hard problem.
One prior solution is to solve the four sub-problems separately. First, the virtual topology is determined and then the routing and wavelength assignment is performed. Finally, the traffic requests are routed. Although this divide-and-conquer method makes traffic grooming easier to handle, it cannot achieve the optimal solution even if an optimal solution is realized for each sub-problem, since these four sub-problems are not necessarily independent and the solution from one sub-problem might affect how optimally another sub-problem can be solved. Sometimes, using the optimal solution for one sub-problem might not lead to the optimal solution to the whole problem. Moreover, this approach requires all the traffic request to be known in advance, which cannot be satisfied in dynamic grooming.
One solution is to solve the four sub-problems as a whole. By taking into account all the constrains regarding the four sub-problems simultaneously, this solution has a potential to achieve better performance. One prior solution with static traffic is formulated as an integer linear program (ILP). An optimal solution can be acquired for some relatively small networks. One problem with ILP is that ILPs are not scalable and cannot be directly applied to large networks.
Prior solutions for traffic grooming have mainly focused on SONET/WDM ring networks. Many of these solutions in static traffic grooming minimize the number of add-drop multiplexers (ADMs) because the ADMs are a major cost in the network. The general traffic-grooming problem in a SONET/WDM ring network is proven to be NP-complete. Unfortunately, many of these prior solutions focus on static traffic only. Some prior solutions use an optimal algorithm for a single-hub ring and several optimal or near-optimal algorithms for traffic grooming and wavelength assignment to reduce the number of wavelengths and SONET ADMs. One prior solution minimizes the network cost, which is dominated by SONET ADMs, in an optical add-drop wavelength-division-multiplexed (OADM) ring network. This solution includes six optical WDM ring architectures and compares the cost of different architectures, as well as the switching capabilities of different architectures under various traffic assumptions.
One prior solution grooms with arbitrary traffic in Bidirectional-Line-Switched-Rings (BLSRs). One prior solution provides a framework used to evaluate the performance of heuristics and requiring less computation than evaluating the optimal solution based on a general formulation of the virtual topology problem. Another prior solution formulates the grooming optimization problem as an integer linear program (ILP) and compare single-hop grooming and multi-hop grooming. One prior solution uses interconnected WDM rings instead of single-ring architectures and uses several strategies for traffic grooming in such networks. One problem with the majority of the prior solution is the focus on static traffic. One prior solution does address the dynamic traffic-grooming problem in SONET/WDM rings and formulates it as a bipartite graph-matching problem.
As fiber-optic backbone networks migrate from rings to mesh, traffic grooming on WDM mesh networks becomes an extremely important area of research. One prior solution formulates static traffic grooming problem as an ILP and proposes a heuristic to minimize the number of transceivers. Another prior solution presents several lower bounds for regular topologies and develops greedy and iterated greedy schemes. However, one problem with these two prior solutions is the relaxation of physical topology constraints and the assumption that all the virtual topologies are implementable on the given physical topology. These two prior solutions do not consider lightpath routing and wavelength assignment. One prior solution uses several node architectures for supporting traffic grooming in WDM mesh networks and formulas the static traffic-grooming problem as an ILP. This solution uses two heuristics and compares the performance with that of the ILP.
Some prior solutions consider a dynamic traffic pattern in WDM mesh networks. One such solution use a connection admission control scheme to fairness in terms of connection blocking. Another solution provides a theoretical capacity correlation model to compute the blocking probability for WDM networks with constrained grooming capability. Another prior solution use two possible route computation algorithms and proposes that, in order to achieve good performance in a dynamic environment, different grooming policies and route-computation algorithms need to be used under different network states. Another prior solution addresses how to dynamically establish reliable low-rate traffic in WDM mesh networks with traffic grooming and compares two grooming schemes. Another prior solution studies how to plan and design a WDM mesh network with certain forecast traffic demands to satisfy all the connections as well as minimize the network cost. Another prior solution investigates how to design multi-layer mesh networks to satisfy the connections"" bandwidth and protection requirement while minimizing the overall network cost.
The WDM backbone network is expected to emerge as a multi-vendor, heterogenous network. As WDM networks migrate from ring topology to mesh topology, it is very important to solve the traffic grooming problem in a heterogeneous mesh network environment.
In terms of wavelength-conversion capability, heterogeneity means that some of the nodes in a network may have a full wavelength-conversion capability (any incoming wavelength can be converted into any outgoing wavelength), some may have no wavelength-conversion capability (traffic must stay in the same wavelength when bypassing these nodes), and some may have partial wavelength-conversion capability (some wavelengths can be converted into some wavelengths). In previous work, however, it was assumed that the nodes in a network either all have wavelength conversion capability or none has wavelength-conversion capability. In addition, if a node has this capability, it always has fill wavelength-conversion capability. This all-or-nothing assumption may not be practical or valid in the future WDM network. It is necessary to address the partial and sparse wavelength-conversion scenarios.
In a WDM mesh network, each node must support two functionalities: wavelength routing, which can be accomplished by an optical crossconnect (OXC), and optical multiplexing/demultiplexing, by which several wavelengths can be multiplexed to or demultiplexed from the same fiber-link. Besides, in order to groom low-speed connections onto a high-speed wavelength channel, a node will need to employ access stations, which can multiplex/demultiplex and switch low-speed connections using various multiplexing techniques, e.g. time-division multiplexing (TDM). A WDM mesh network may consist of systems from multiple vendors, and different vendors may employ different node architectures, which may have different grooming capabilities. Some architectures may have full grooming capabilities, while some may impose some constraints, such as the number of grooming ports (represented by the number of transceivers used for originating and terminating groomable wavelength channels), on the grooming capability. These partial and sparse scenarios are very practical and should also be considered when solving the traffic-grooming problem.
To solve the traffic-grooming problem, the integrated approach is desirable not only because it has the potential to achieve better performance than the separated approach, but also because it can be used directly for dynamic traffic grooming where the separated approach cannot be used. For a given connection request, the integrated approach should address the following issues: (1) should this connection be routed on the current virtual topology if it is possible to do so? Sometimes, it may be better to set up a new lightpath even though the connection can be carried on the current virtual topology. (2) How to change the virtual topology to accommodate the connection? i.e. between which two nodes should we set up a new lightpath, if any? In some cases, we can set up a light directly between the source of the traffic to the destination. In other cases, it is not necessary or possible to set up this lightpath and we may need to set up one or more lightpaths and route the connection onto these lightpaths and/or some existing lightpaths. Different decisions on these questions can result in different network performance. These decisions reflect the intentions of the network operator, and they are referred to as grooming policies. By using different grooming policies, a network operator can achieve various objectives, such as minimizing the number of wavelength-links, minimizing the number of lightpaths, minimizing the traffic hops on the virtual topology, etc. As the network state changes, the optimization objective may also need to change. Dynamically evolving the grooming policy according to the network state is also a challenge for traffic grooming.
The inventions solve the above problems by using a software model to operate an optical communication network with a plurality of optical nodes wherein the optical communication network use wavelength division multiplexing. A software model of the optical communication network is generated wherein the optical nodes are represented by access layers with access input ports and access output ports, lightpath layers with lightpath input ports and lightpath output ports and wavelength layers for each wavelength with wavelength input ports and wavelength output ports. The graphical links are then generated between the access input ports, the access output ports, the lightpath input ports, the lightpath output ports, the wavelength input ports, and the wavelength output ports based on capabilities of the optical nodes. A path is determined for communications between a source one of the optical nodes and a destination one of the optical nodes wherein the path is between one of the access output ports of the source one to the one of the access input ports of the destination one through either the lightpath layers or the wavelength layers based on the software model. A determination is then made of whether the path passes through any of the wavelength layers. A lightpath link is then generated for the graphical link of the path that pass through the wavelength layers and the wavelength corresponding to the wavelength layer is assigned to the lightpath.
In some embodiments, the optical communication network is in a mesh configuration. In some embodiments, a request is received for communications between a source one of the optical nodes and a destination one of the optical nodes. In some embodiments, weights are assigned to the graphical links. In other embodiments, the graphical links are deleted based on the capabilities of the optical nodes.
The inventions advantageously solves four sub-problems jointly: (1) determining the virtual topology that consists of lightpaths, (2) routing the lightpaths over the physical topology, (3) performing wavelength assignment to the lightpaths, and (4) routing the traffic on the virtual topology. In some embodiments, the graphical links and weights of these graphical links are manipulated to achieve various objectives using different grooming policies, while taking into account various constraints such as transceivers, wavelengths, wavelength conversion capabilities, and grooming capabilities. Also, the inventions may be applied to both static and dynamic traffic grooming.